package algorithm.SkipInArray;

/*
给出一组正整数arr，
每个数的值表示你从这个位置可以向右跳跃的最大长度，
计算如何以最少的跳跃次数跳到最后一个数
 */
public class SkipInArray {
    public static int skip(int[] arr) {
        int curMax = 0;
        int nextMax = -1;
        int step = 0;

        int cur = 0;
        while (cur < arr.length) {
            for (; cur <= curMax && cur < arr.length; cur++) {
                nextMax = Math.max(nextMax, arr[cur] + cur);
            }
            curMax = nextMax;
            nextMax = -1;
            step++;
        }

        return step;
    }

    public static void main(String[] args) {
        System.out.println(skip(new int[]{3, 1, 4, 2, 1, 1, 5, 2, 1, 1}));
    }
}
